// @algorithm @lc id=100308 lang=cpp
// @title zi-fu-chuan-de-pai-lie-lcof

#include "algm/algm.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    vector<string> ans;
    vector<bool> visited;
    vector<string> permutation(string s) {
        int n = s.size();
        visited.resize(n);
        sort(s.begin(), s.end());
        string perm;
        backtracking(s, 0, n, perm);
        return ans;
    }

    void backtracking(const string &s, int i, int n, string &perm) {
        if (i == n) {
            ans.push_back(perm);
            return;
        }
        for (int j = 0; j < n; ++j) {
            if (visited[j] || (j > 0 && visited[j - 1] && s[j - 1] == s[j])) {
                continue;
            }
            visited[j] = true;
            perm.push_back(s[j]);
            backtracking(s, i + 1, n, perm);
            perm.pop_back();
            visited[j] = false;
        }
    }
};